package gold.digger;

import gold.utils.InputUtil;
import gold.vo.TreeNode;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC971 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
            List<Integer> ans = new ArrayList<>();
            int nextPos = preVisit(root, ans, 0, voyage);
            if (nextPos >= voyage.length) return ans;
            else return new ArrayList<>(Arrays.asList(-1));
        }

        public int preVisit(TreeNode root, List<Integer> ans, int curPos, int[] voyage) {
            if (curPos >= voyage.length || root.val != voyage[curPos]) return -1;
            if (null == root.left && null == root.right) return curPos + 1;
            if (null == root.left && null != root.right) return preVisit(root.right, ans, curPos + 1, voyage);
            if (null == root.right && null != root.left) return preVisit(root.left, ans, curPos + 1, voyage);
            // 左右字树头节点都不为空，判断是否匹配互换
            if (root.left.val == voyage[curPos + 1]) {
                int nextPos = preVisit(root.left, ans, curPos + 1, voyage);
                if (-1 == nextPos) return -1;
                return preVisit(root.right, ans, nextPos, voyage);
            } else if (root.right.val == voyage[curPos + 1]) {
                // 命中 需要左右互换情况
                ans.add(root.val);
                int nextPos = preVisit(root.right, ans, curPos + 1, voyage);
                if (-1 == nextPos) return -1;
                return preVisit(root.left, ans, nextPos, voyage);
            }

            return -1;
        }
    }

    public void run() {
        Solution solution = new Solution();
//        System.out.println(solution.flipMatchVoyage(TreeNode.createTree("[1,2,3]"), InputUtil.toIntegerArray("[1,3,2]")));
//        System.out.println(solution.flipMatchVoyage(TreeNode.createTree("[1,2,3]"), InputUtil.toIntegerArray("[1,2,3]")));
        System.out.println(solution.flipMatchVoyage(TreeNode.createTree("[15,26,40,25,38,29,6,48,1,16,8,18,27,21,19,31,39,46,null,49,45,null,22,34,41,42,null,9,null,2,4,null,null,null,17,null,null,null,null,36,24,null,33,null,30,null,null,23,37,null,null,5,12,null,10,7,null,null,null,13,null,null,null,11,43,null,null,null,null,null,null,50,35,3,32,null,null,null,null,null,null,null,null,null,47,null,28,44,14,null,null,null,null,null,20]"), InputUtil.toIntegerArray("[15,40,6,21,9,19,2,12,50,47,35,28,20,5,4,10,32,3,14,44,29,18,34,7,11,43,41,27,42,37,23,26,38,16,45,24,13,36,49,8,22,33,25,1,46,48,31,39,17,30]")));
    }

    public static void main(String[] args) throws Exception {
        LC971 an = new LC971();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
